// Created by Jisam on 2024/8/15 20:25.
// solve P1083 [NOIP2012 提高组] 借教室
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>

#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define ui unsigned
#define lli long long
#define ulli unsigned long long
#define int long long
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

// 定义全局变量
int n, m; // n表示仓库数量，m表示请求数量

// 定义数组以记录不同时间段内的库存变化和需求情况
int diff[1000011], need[1000011], rest[1000011], r[1000011], l[1000011], d[1000011];

/**
 * 检查给定的请求数量x是否可行
 * @param x 指定的请求数量
 * @return 如果请求数量可行返回true，否则返回false
 */
bool isok(int x)
{
    memset(diff, 0, sizeof(diff)); // 初始化diff数组为0，表示没有库存变化

    // 遍历前x个请求，更新diff数组以反映库存变化
    for(int i = 1; i <= x; i++)
    {
        diff[l[i]] += d[i]; // 在请求开始位置增加库存
        diff[r[i] + 1] -= d[i]; // 在请求结束位置之后减少库存
    }

    // 遍历每个仓库，计算累计需求量并检查是否超过库存
    for(int i = 1; i <= n; i++)
    {
        need[i] = need[i - 1] + diff[i]; // 计算当前仓库的累计需求量
        if(need[i] > rest[i]) return false; // 如果需求量超过库存，则请求不可行
    }

    return true; // 所有仓库的需求都满足，请求可行
}

signed main()
{
    scanf("%d%d", &n, &m); // 输入仓库数量和请求数量

    // 输入每个仓库的库存量
    for(int i = 1; i <= n; i++) scanf("%d", &rest[i]);

    // 输入每个请求的详细信息：需求量、起始仓库、结束仓库
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &l[i], &r[i]);

    int begin = 1, end = m; // 定义二分查找的起始和结束位置

    // 如果m个请求即可满足，则输出0并结束程序
    if(isok(m)){ cout << "0"; return 0; }

    // 使用二分查找确定最少需要撤销的请求数量
    while(begin < end)
    {
        int mid = (begin + end) / 2; // 计算中间位置
        if(isok(mid)) begin = mid + 1; // 如果mid个请求可行，则查找后半部分
        else end = mid; // 否则，查找前半部分
    }

    // 输出结果：最少需要撤销的请求数量
    cout << "-1" << endl << begin;
}

